package com.code.leetcode._202504;

import com.code.leetcode._202503.ListNode;

import java.util.PriorityQueue;

/**合并K个升序链表 **/
public class MergeList {

    public ListNode mergeKLists(ListNode[] lists) {
        // 准备一个头节点
        ListNode dummy = new ListNode(-1), tail = dummy;
        //准备一个升序队列
        PriorityQueue<ListNode> q = new PriorityQueue<>((a, b)->a.val-b.val);
        //将所有的节点放入PriorityQueue 中
        for (ListNode node : lists) {
            if (node != null) q.add(node);
        }
        while (!q.isEmpty()) {
            //获取头节点 将头节点放入dummy里面
            ListNode poll = q.poll();
            tail.next = poll;
            tail = tail.next;
            //将已经放入的节点删除
            if (poll.next != null) q.add(poll.next);
        }
        return dummy.next;
    }

}
